package BurstBalloons;



public class Solution {
    public int maxCoins(int[] nums) {
    	if (nums==null||nums.length==1) return 0;
    	if (nums.length==1) return nums[0];
        int[][] f=new int[nums.length+3][nums.length+3];
        int[] numss=new int[nums.length+2];
        numss[0]=1;
        for (int i=1;i<=nums.length;i++)
        	numss[i]=nums[i-1];
        numss[nums.length+1]=1;
        nums=numss;

        for (int i=2;i<nums.length;i++)
        	for (int left=0;left+i<nums.length;left++)
        		for (int m=left+1;m<left+i;m++){
        			f[left][left+i]=Math.max(f[left][left+i], f[left][m]+f[m][left+i]+nums[m]*nums[left]*nums[left+i]);
        		}
        return f[0][nums.length-1];
    }
    public static void main(String args[]) {
		int[] t={9};
		Solution so=new Solution();
		so.maxCoins(t);
		System.out.println(so.maxCoins(t));
	}
}

/*题意 给定一串气球 每个气球上有数字 击破某个气球可获得 num[i-1]*num[i]*num[i+1]的分数 求解最大分
    dp[i][j]表示[i,j]范围内可得的最大分数且最后剩余 气球i,j没破
    转移方程如上*/

